<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "https://www.w3.org/TR/html4/loose.dtd">
<html lang="zh-CN"><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"><meta http-equiv="Content-Language" content="zh-CN"><link href="stylesheet.css" media="all" rel="stylesheet" type="text/css">
<title>PostgreSQL 里的基因查询优化(GEQO)</title>
<script> var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?d286c55b63a3c54a1e43d10d4c203e75"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); </script>
</head><body class="SECT1">
<div>
<table summary="Header navigation table" width="100%" border="0" cellpadding="0" cellspacing="0">
<tr><th colspan="5" align="center" valign="bottom">PostgreSQL 8.2.3 中文文档</th></tr>
<tr><td width="10%" align="left" valign="top"><a href="geqo-intro2.html" accesskey="P">后退</a></td><td width="10%" align="left" valign="top"><a href="geqo.html">快退</a></td><td width="60%" align="center" valign="bottom">章48. 基因查询优化器</td><td width="10%" align="right" valign="top"><a href="geqo.html">快进</a></td><td width="10%" align="right" valign="top"><a href="geqo-biblio.html" accesskey="N">前进</a></td></tr>
</table>
<hr align="LEFT" width="100%"></div>
<div class="SECT1"><h1 class="SECT1"><a name="GEQO-PG-INTRO">48.3. PostgreSQL 里的基因查询优化(GEQO)</a></h1>
<p>GEQO 模块是试图解决类似漫游推销员问题(TSP)的查询优化问题的。可能的查询规划被当作整数字符串进行编码。每个字符串代表查询里面一个关系到下一个关系的连接的顺序。例如，下面的连接树</p>
<pre class="LITERALLAYOUT">   /\
  /\ 2
 /\ 3
4  1</pre>
<p>是用整数字符串'4-1-3-2'编码的，这就是说，首先连接关系'4'和'1'，然后'3'，然后是'2'，这里的 1, 2, 3, 4 都是 PostgreSQL 优化器里的关系标识(ID)。</p>
<p>GEQO 模块的一部分是采用的 D.Whitley 的 Genitor 算法。</p>
<p>在 PostgreSQL 里的 GEQO 实现的一些特性是：</p>
<ul compact="COMPACT">
<li style="list-style-type: disc"><p>使用<i class="FIRSTTERM">稳定状态</i>的 GA(替换全体中最小适应性的个体，而不是整代的替换)允许向改进了的查询规划快速逼近。这一点对在合理时间内处理查询是非常重要的；</p></li>
<li style="list-style-type: disc"><p><i class="FIRSTTERM">边缘重组交叉</i>的使用特别适于在用 GA 解决 TSP 问题时保持边缘损失最低。</p></li>
<li style="list-style-type: disc"><p>否决了把突变作为基因操作符的做法，这样生成合法的 TSP 漫游时不需要修复机制。</p></li>
</ul>
<p>GEQO 模块让 PostgreSQL 查询优化器可以通过非穷举搜索有效地支持大的连接查询。</p>
<div class="SECT2"><h2 class="SECT2"><a name="GEQO-FUTURE">48.3.1. PostgreSQL GEQO 未来的实现任务</a></h2>
<p>还需要一些工作来改进基因算法的参数设置。在文件 <tt class="FILENAME">src/backend/optimizer/geqo/geqo_main.c</tt> 里的过程 <code class="FUNCTION">gimme_pool_size</code> 和 <code class="FUNCTION">gimme_number_generations</code> 在设置参数时不得不为两个竞争需求做出折衷：</p>
<ul compact="COMPACT">
<li><p>查询规划的优化</p></li>
<li><p>计算处理时间</p></li>
</ul>
<p>在最基本的层面上，并不清楚用给 TSP 涉及的 GA 算法解决查询优化的问题是否合适。在 TSP 的情况下，与任何子字符串(部分旅游)相关的开销都是独立于旅游的其它部分的，但是目前，这一点对于查询优化是不同的。因此，可以怀疑边缘重组交叉是否最有效的突变过程。</p>
</div>
</div>
<div>
<hr align="LEFT" width="100%">
<table summary="Footer navigation table" width="100%" border="0" cellpadding="0" cellspacing="0">
<tr><td width="33%" align="left" valign="top"><a href="geqo-intro2.html" accesskey="P">后退</a></td><td width="34%" align="center" valign="top"><a href="index.html" accesskey="H">首页</a></td><td width="33%" align="right" valign="top"><a href="geqo-biblio.html" accesskey="N">前进</a></td></tr>
<tr><td width="33%" align="left" valign="top">基因算法</td><td width="34%" align="center" valign="top"><a href="geqo.html" accesskey="U">上一级</a></td><td width="33%" align="right" valign="top">进一步阅读</td></tr>
</table>
</div>
</body></html>